#include<vector>
#include<unordered_map>
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
	unordered_map<int, vector<TreeNode*>> memory;

public:
	vector<TreeNode*> allPossibleFBT(int N) {
		if (memory.find(N) != memory.end())
			return memory[N];
		if (N == 1) memory[N].push_back(new TreeNode(0));
		else {
			if (N % 2 == 1) {
				for (int i = 0; i < N; ++i) {
					int j = N - i - 1;
					for (auto left : allPossibleFBT(i)) {
						for (auto right : allPossibleFBT(j)) {
							TreeNode* root = new TreeNode(0);
							root->left = left;
							root->right = right;
							memory[N].push_back(root);
						}
					}
				}
			}
		}
		return memory[N];
	}
};
